package opdracht3;

public class RedBlackTree<K extends Comparable<K>, V> {

	private Node root;
	private final static boolean RED = true;
	private final static boolean BLACK = false;

	public void insert(K key, V value) {
		root = insert(root, key, value);
		root.color = BLACK;
	}

	public Node insert(Node node, K key, V value) {
		if (node == null) {
			return new Node(key, value, RED);
		}
		int compare = key.compareTo(node.key);
		if (compare < 0) {
			node.left = insert(node.left, key, value);
		} else if (compare > 0) {
			node.right = insert(node.right, key, value);
		} else {
			node.value = value;
		}

		balanceTree(node);

		return node;
	}

	public V search(K key) {
		return search(key, root);
	}

	public V search(K key, Node node) {
		int comp = key.compareTo(node.key);
		if (comp == 0) {
			return node.value;
		} else if (comp > 0) {
			if (node.right != null) {
				return search(key, node.right);
			} else {
				return null;
			}
		} else {
			if (node.left != null) {
				return search(key, node.left);
			} else {
				return null;
			}
		}
	}

	public boolean delete(K key) {
		return delete(key, root);
	}

	public boolean delete(K key, Node node) {
		int comp = key.compareTo(node.key);
		if (comp == 0) {
			if (node.isLeaf()) {
				node = null;
			} else {
				if (node.right != null) {
					node = node.right;
				} else {
					node = node.left;
				}
			}

			return true;
		} else if (comp > 0) {
			if (node.right != null) {
				return delete(key, node.right);
			} else {
				return false;
			}
		} else {
			if (node.left != null) {
				return delete(key, node.left);
			} else {
				return false;
			}
		}
	}

	public void balanceTree(Node node) {
		if (isRed(node.right) && !isRed(node.left))
			node = rotateLeft(node);
		if (isRed(node.left) && isRed(node.left.left))
			node = rotateRight(node);
		if (isRed(node.left) && isRed(node.right))
			flipColors(node);
	}

	private boolean isRed(Node node) {
		if (node == null) {
			return false;
		}
		return (node.color == RED);
	}

	public Node rotateLeft(Node node) {
		if (node.left != null) {
			Node n = node.left.right;
			node.left.right = node;
			node = node.left;
			node.right.left = n;
		}
		return node;
	}

	public Node rotateRight(Node node) {
		if (node.right != null) {
			Node n = node.right.left;
			node.right.left = node;
			node = node.right;
			node.left.right = n;
		}
		return node;
	}

	public void flipColors(Node node) {
		if (node != null && !node.isLeaf()) {
			if ((!isRed(node) && isRed(node.left) && isRed(node.right))
					|| (isRed(node) && !isRed(node.left) && !isRed(node.right))) {
				node.color = !node.color;
				node.left.color = !node.left.color;
				node.right.color = !node.right.color;
			}
		}
	}

	/*
	 * public int height(Node node) {
	 * 
	 * int left = height(node.left); int right = height(node.right);
	 * 
	 * if (left > right) { return left + 1; } else { return right + 1; } }
	 */

	private class Node {

		private K key;
		private V value;
		private Node left;
		private Node right;
		private boolean color;

		public Node(K key, V value, boolean color) {
			this.key = key;
			this.value = value;
			this.color = color;
		}

		public boolean isLeaf() {
			return right == null && left == null;
		}

	}

}
